from typing import List
"""
    给定一个可包含重复数字的序列 nums ，
    按任意顺序 返回所有不重复的全排列。
    
    示例 1：
            输入：nums = [1,1,2]
            输出：
                    [[1,1,2],
                     [1,2,1],
                     [2,1,1]] 
"""

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        ans = []
        tem = []
        used = []

        for i in range(len(nums)):
            used.append(0)
        def backtracking(height):
            if height == len(nums):
                ans.append(tem.copy())
                return
            for i in range(0,len(nums)):
                if i != 0 and nums[i] == nums[i-1] and used[i-1] == 0:
                    continue
                if used[i] == 1:
                    continue
                tem.append(nums[i])
                used[i] = 1
                backtracking(height+1)
                tem.pop()
                used[i] = 0
            return
        backtracking(0)
        return ans